package gsw.tool.arithmetic;

import java.util.Arrays;

import gsw.tool.common.Tool;
import gsw.tool.common.ToolShow;

/**
 * 分治法可以通俗的解释为：把一片领土分解，分解为若干块小部分，然后一块块地占领征服，被分解的可以是不同的政治派别或是其他什么，然后让他们彼此异化。
 * 分治法的精髓：
 * - 分--将问题分解为规模更小的子问题；
 * - 治--将这些规模更小的子问题逐个击破；
 * - 合--将已解决的子问题合并，最终得出“母”问题的解；
 * 分治法的应用：二分查找、快速排序、归并排序、循环赛日程表等。
 *
 * @author Asus
 */
public class DivideConquer {
    public static void test() {
//        //测试二分查找
//        Integer[] arr = new Integer[]{1, 23, 34, 56, 56, 78};
//        int index = binarySearch(arr, 0, arr.length, 34);
//        ToolShow.log(index + ":" + 34);
//
//        //测试快速排序
//        Integer[] arr2 = new Integer[]{7, 23, 6, 1, 7, 78};
//        quicksort(arr2, 0, arr2.length - 1);
//        ToolShow.printArr(arr2);

//        //测试快速排序
//        Integer[] arr3 = new Integer[]{7, 23, 6, 1, 7, 78};
//        megreSort(arr3, 0, arr3.length - 1);
//        ToolShow.printArr(arr3);

        //测试循环赛日程表
        int[][] arr = DivideConquer.cyclingRace(3);
        ToolShow.printArr(arr);
    }

    /**
     * 分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。
     * 查找过程：
     * 首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，
     * 如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，
     * 或直到子表不存在为止，此时查找不成功。
     *
     * @param arr   被查找的数组
     * @param start 查找开始的位置
     * @param end   查找结束的位置(不包含)
     * @param data  要查找的数据
     * @return 查找数据在数组中的下标
     */
    public static <E extends Comparable<E>> int binarySearch(E[] arr, int start, int end, E data) {
        if (Tool.isEmpty(arr)) {
            return -1;
        }
        int low = start;
        // 包左不包右
        int high = end - 1;

        while (low < high) {
            int mid = (low + high) >>> 1;
            if (arr[mid].compareTo(data) == 0) {
                return mid;
            } else if (arr[mid].compareTo(data) > 0) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return -low;// 返回最后查找的位置
    }

    /**
     * 快速排序（Quicksort）是对冒泡排序的一种改进。
     * 快速排序由C. A. R. Hoare在1962年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
     * 快速排序:适用于数据量大的顺序表
     * 为什么不适合链式表？
     * 1. 快速排序的过程，主要是查找比较数据，修改少；
     * 2. 快速排序是从两端查找比较，如果是单链表，性能会更差。
     *
     * @param arr：需要排序的数组
     * @param start:开始排序的位置
     * @param end:结束排序的位置(包含)
     */
    public static <E extends Comparable<E>> void quicksort(E[] arr, int start, int end) {
        if (Tool.isEmpty(arr) || start >= end) {
            return;
        }

        int low = start;
        int high = end;
        //基准值
        E data = arr[start];
        //从两端开始，与基准值比较，小于基准值就放在左边，大于基准值就放在右边
        while (low < high) {
            //先找比基准值小的数据
            while (low < high && data.compareTo(arr[high]) <= 0) {
                high--;
            }
            //将小的数据放到左边
            arr[low] = arr[high];
            //再找比基准值小的数据
            while (low < high && data.compareTo(arr[low]) >= 0) {
                low++;
            }
            //将大的数据放到右边
            arr[high] = arr[low];
        }
        //low即为基准值的下标
        arr[low] = data;
        //对左边的数据进行快速排序
        quicksort(arr, start, low - 1);
        //对边的数据进行快速排序
        quicksort(arr, low + 1, end);
    }

    /**
     * 归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
     * 归并过程为：比较a[i]和b[j]的大小，若a[i]≤b[j]，则将第一个有序表中的元素a[i]复制到r[k]中，并令i和k分别加上1；否则将第二个有序表中的元素b[j]复制到r[k]中，并令j和k分别加上1，如此循环下去，直到其中一个有序表取完，然后再将另一个有序表中剩余的元素复制到r中从下标k到下标t的单元。
     * 归并排序的算法我们通常用递归实现，先把待排序区间[S,t]以中点二分，接着把左边子区间排序，再把右边子区间排序，最后把左区间和右区间用一次归并操作合并成有序的区间[S,t]。
     * 归并排序适用于数据量大的链表,占用内存比快速排序大。
     *
     * @param arr：需要排序的数组
     * @param start:开始排序的位置
     * @param end:结束排序的位置(包含)
     */
    public static <E extends Comparable<E>> void megreSort(E[] arr, int start, int end) {
        if (arr == null || arr.length == 0) {
            return;
        }

        if (start >= end) {
            return;
        }
        //二进制右移，相当于除以2
        int mid = (start + end) >>> 1;
        //先把左边排好序
        megreSort(arr, start, mid);
        //再把右边排好序
        megreSort(arr, mid + 1, end);

        //创建一个临时数组，用于拷贝数据
        E[] copy = Arrays.copyOf(arr, arr.length);
        int i = start;
        int j = mid + 1;
        //把左右两边合在一起：左边的数可能大于右边
        for (int k = start; k <= end; k++) {
            //将小的数据放到arr中
            if (i <= mid && copy[i].compareTo(copy[j]) < 0) {
                arr[k] = copy[i];
                i++;
                //左边的表中数据放完后，就直接放右表数据
            } else if (i > mid && copy[i].compareTo(copy[j]) < 0) {
                arr[k] = copy[j];
                j++;
            } else if (j <= end && copy[i].compareTo(copy[j]) >= 0) {
                arr[k] = copy[j];
                j++;
                //右边的表中数据放完后，就直接放左表数据
            } else if (j > end && copy[i].compareTo(copy[j]) >= 0) {
                arr[k] = copy[i];
                i++;
            }
        }
    }

    /**
     * 循环赛日程表问题是指，设有n=2＾k个选手参加比赛，要求设计一个满足一下要求的比赛日程表:
     * 1. 每个选手必须与其他的n-1个选手个比赛一次；
     * 2. 每个选手每天只能赛一次 。
     * 解决思路：
     * 1. 先将选手两两分组，直到每组只有两名选手；
     * 2. 然后对每组的两名选手安排赛程，先创建一个二维数组A，然后把二名选手按序号放到A的第一行，然后把1号选手复制到A的右下角，把2号选手复制到A的左下角，现在A的排序就是这两名选手的日程表；
     * 3. 然后把上面的分组再两两合并一次，那么新的分组由之前的两个小分组组成，将这两个小分组当成2个单位，参照步骤2对他们排序，排序结果就是它们的日程表；
     * 4. 重复步骤2和3，知道全部排好序。
     *
     * @param k 选手个数的2次幂
     * @return 日程表
     */
    public static int[][] cyclingRace(int k) {
        // 选手个数
        int n = 1 << k;
        //日程表
        int[][] result = new int[n][n];
        // 初始化日程表
        for (int j = 0; j < n; ) {
            result[0][j] = ++j;
        }

        //先两两分组，排好序后，再两两合并，继续排序
        for (int i = 0; i < k; i++) {
            int len = 1 << i;
            for (int j = 0; j < n; j += len * 2) {
                // 将二维数组左上部分复制到右下部分
                copyArr(result, 0, j, len, j + len, len);
                // 将二维数组右上部分复制到左下部分
                copyArr(result, 0, j + len, len, j, len);
            }
        }
        return result;
    }

    /**
     * 拷贝二维数组
     *
     * @param arr：被拷贝的二维数组
     * @param a1：二维数组左上角的横坐标
     * @param a2：二维数组左上角的纵坐标
     * @param b1：二维数组右下起点的横坐标
     * @param b2：二维数组右下起点的纵坐标
     * @param len:拷贝的长度
     */
    public static void copyArr(int[][] arr, int a1, int a2, int b1, int b2, int len) {
        for (int i = 0; i < len; i++) {
            for (int j = 0; j < len; j++) {
                arr[b1 + i][b2 + j] = arr[a1 + i][a2 + j];
            }
        }
    }
}
